public class QuickSort {
    //https://blog.csdn.net/shujuelin/article/details/82423852
    static void quickSort(int[] nums, int left, int right) {
        if (left >= right)
            return;
        int pivot = parttion(nums, left, right);
        quickSort(nums, left, pivot - 1);
        quickSort(nums, pivot + 1, right);
    }

    static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    //哨兵划分
    static int parttion(int[] nums, int left, int right) {
        //以nums[left]为基准数
        int i = left;
        int j = right;
        while (i < j) {
            while (i < j && nums[j] >= nums[left]) {
                j--;
            }
            while (i < j && nums[i] <= nums[left]) {
                i++;
            }
            swap(nums, i, j);
        }
        swap(nums, i, left);
        return i;
    }

    public static void main(String[] args) {
        int[] arr = {1, 0, 2, 4, 3, 5};
        quickSort(arr, 0, arr.length - 1);
        for (int j : arr) {
            System.out.println(j);
        }
    }
}